86. 分隔链表

Similar Question

leading to the advanced question

Solution Tips

双虚拟头

方案一: 模拟

var partition = function(head, x) {
    // 双指针, 需要有一个指针指着可以插入的位置, 另一个指针去找要插入的元素
    // 有点快慢指针的意思, 但是其实不是, 就是单纯的双指针而已, 归类为分段指针
    // 原地操作指针太多, 太复杂了, 不如归并, 最后拼接两个链表就 ok
    let small = new ListNode(0);
    const smallHead = small;
    let large = new ListNode(0);
    const largeHead = large;
    while (head !== null) {
        if (head.val < x) {
            small.next = head;
            small = small.next;
        } else {
            large.next = head;
            large = large.next;
        }
        head = head.next;
    }
    large.next = null;
    small.next = largeHead.next;
    return smallHead.next;


    // let low = dummy;
    // let prev = head;
    // let high = head;
    // // 第一个大于等于 x 的节点一直都是 highHead
    // let highHead = null;

    // while (high !== null) {
    //     if (high.val < x) {
    //         low.next = high;
    //         low = low.next;
    //         // high 的前一个节点要拼接下一个才行
    //         prev.next = high.next;
    //     }
    //     else if (highHead === null) {
    //         highHead = high;
    //     }
    //     else {
    //         prev = high;
    //     }
    //     high = high.next;
    // }

    // low.next = highHead;

    return dummy.next;
};